package com.demo.alg.chapter15动态规划.最长递增子序列;

public class Dp06 {

	public static void main(String[] args) {
		int[] num = new int[]{5, 1, 6, 8, 2, 4, 5, 10};
		int n = num.length;

		double[] dou = new double[n + 1];
		dou[0] = Integer.MIN_VALUE;
		dou[1] = num[0];
		int Len = 1;
		int p, r, m;
		for (int i = 1; i < n; i++) {
			p = 0;
			r = Len;
			while (p <= r) {
				m = (p + r) / 2;
				if (dou[m] < num[i]) {
					p = m + 1;
				} else {
					r = m - 1;
				}
			}
			dou[p] = num[i];
			if (p > Len) {
				Len++;
			}
		}
		System.out.println(Len);
	}

}
